package com.yuan.algorithms.第七届蓝桥杯;

/*
 对于每一个正整数，如果它是奇数，则对它乘3再加1，如果它是偶数，则对它除以2，如此循环，最终都能够得到1。
 输入一个整数N(1<N<5000000)，请你计算从1~N的数进行变化时出现的最大值。
 例如：
 N=9
 9 > 28 > 14 > 12 > 6 > 3 > 10 > 5 > 16 > 8 > 4 > 2 > 1 最大值是28
 N=11
 11 > 34 > 17 > 52 > 26 > 13 > 40 > 20 > 10 > 5 > 16 > 8 > 4 > 2 > 1 最大值是52
 */
import java.util.Scanner;

/**
 * @author YouYuan
 * @contact 1265161633@qq.com
 * @date 2016年3月20日 下午2:36:31
 * @descript 冰雹数求变化中的最大值，解题策略：保存已知的数变化到1出现的最大的数，下次其它数变化成了这个数时就可以不用重复求解了。 问题：如何保存一个数变化为1的过程中出现的最大值？
 */
public class 冰雹数 {

	static Scanner in = new Scanner(System.in);
	static int SIZE = 5000000 * 20;
	static long[] map = new long[SIZE];

	public static void main(String[] args) {
		while (in.hasNext()) {
			int n = in.nextInt();
			rs1(n);
			rs2(n);
		}
	}

	private static void rs2(int n) {
		long max = 0;
		for (int i = n; i > 0; i--) {
			long t = i;
			do {
				max = t > max ? t : max;
				if ((t & 1) == 1) {
					t = t * 3 + 1;
				} else {
					t >>= 1;
				}
			} while (t != 1);
		}
		System.out.println("Rs2:" + max);
	}

	private static void rs1(int n) {
		long max = 0;
		for (int i = n; i > 0; i--) {
			long k = f(i, i);
			if (k > max) {
				max = k;
			}
		}
		System.out.println("Rs1:" + max);
	}

	private static long f(long temp, long max) {
		if (temp == 1) {
			return max;
		}
		if (temp < map.length && map[(int) temp] != 0) {
			return map[(int) temp];
		}
		long tMax = 0;
		if ((temp & 1) == 1) {
			temp = temp * 3 + 1;
		} else {
			temp = temp >> 1;
		}
		tMax = Math.max(temp, max);
		if (temp < map.length) {
			if (map[(int) temp] != 0) {
				return Math.max(map[(int) temp], tMax);
			}
			map[(int) temp] = f(temp, temp);
			return Math.max(map[(int) temp], tMax);
		}
		return tMax;
	}
}
